package 牛客网在线编程题库;

/**
 * 将两个有序的链表合并为一个新链表，要求新的链表是通过拼接两个链表的节点来生成的，且合并后新链表依然有序。
 * 示例1
 * 输入
 * {1},{2}
 * 返回值
 * {1,2}
 * 示例2
 * 输入
 * {2},{1}
 * 返回值
 * {1,2}.
 */

//class ListNode {
//    int val;
//    ListNode next = null;
//
//    ListNode(int val) {
//        this.val = val;
//    }
//}

public class _合并有序链表 {
    public ListNode mergeTwoLists (ListNode l1, ListNode l2) {
        // write code here
        if (l1 == null && l2 == null) {
            return null;
        }
        // 定义新链表的头指针
        ListNode head = new ListNode(0);
        // 新链表的遍历指针
        ListNode cur = head;
        // 当两条链表一条遍历完循环停止
        while (l1 != null && l2 != null) {
            // 链表1值小于链表2
            if (l1.val <= l2.val) {
                // 连接到目标链表
                cur.next = l1;
                // 单链表指针后移
                l1 = l1.next;
            }else {
                cur.next = l2;
                l2 = l2.next;
            }
            // 目标链表指针后移
            cur = cur.next;
        }
        if (l1 != null) {
            cur.next = l1;
        }else{
            cur.next = l2;
        }
        return head.next;
    }
}
